import random
import numpy as np
import copy
import pandas as pd
import time
import csv

T = 0
while T < 100:

    def get_list_index(time_list):
        sorted_indices = sorted(range(len(time_list)), key=lambda i: time_list[i])
        ranked_list = [sorted_indices.index(i) + 1 for i in range(len(time_list))]
        return ranked_list


    def create_chromosome(task_num, robot_num):
        # 5 robot
        robot_seq = [np.random.randint(6) for _ in range(task_num * 2)]
        # 20 --> 30 task
        unique_numbers = random.sample(range(40), 40)
        task_seq = unique_numbers + unique_numbers
        random.shuffle(task_seq)
        return np.vstack((robot_seq, task_seq))


    def create_population(task_num, robot_num, pop_num):
        return np.stack([create_chromosome(task_num, robot_num) for _ in range(pop_num)])


    def distance(x1, x2):
        return np.abs(x1[0] - x2[0]) + np.abs(x1[1] - x2[1])


    def time_restrict(list1):
        list_sort = []
        for index,t in enumerate(list1):
            list_sort.append([index,t])
            task_seq = pd.DataFrame(list_sort)
            task_seq.columns = ['task', 'finished time']
            task_seq = task_seq.sort_values(by='finished time')
            for i in range(len(task_seq)):
                if i > 0:
                    time_1 = task_seq.iloc[i,1] - task_seq.iloc[i-1,1]
                    if time_1 < tasks_time[i]:
                        task_seq.iloc[i,1] += abs(tasks_time[i] - time_1)
        return task_seq


    def method1(dict2, robot_time, time_list, time_list2):
        dict3 = copy.deepcopy(dict2)
        # 5 robot
        for j in range(6):
            rob = str(j)
            if rob in dict3:
                time = robot_time[j]
                for i in range(len(dict3[rob])):
                    if dict3[rob][i][1] == 1:
                        task_index = dict3[rob][i][0]
                        time_list[task_index] = distance(robots_positions[j], tasks[task_index]) + time + distance(tasks[task_index], packing_position)
                        time = time_list[dict3[rob][i][0]]
                        robots_positions[j] = packing_position
                        dict2[rob].remove(dict3[rob][i])
                        robot_time[j] = time_list[dict3[rob][i][0]]
                    if dict3[rob][i][1] == 2:
                        break
        return dict2, robot_time, time_list, time_list2


    def method2(dict2, robot_time, time_list, time_list2):
        dict4 = copy.deepcopy(dict2)
        # 5 robot
        for j in range(6):
            rob = str(j)
            if rob in dict4:
                for i in range(len(dict4[rob])):
                    if dict4[rob][i][1] == 2:
                        task_index = dict4[rob][i][0]
                        task_2_start = max(time_list[task_index], robot_time[j])
                        if task_2_start == 99999:
                            break
                        else:
                            time_list2[task_index] = task_2_start + distance(robots_positions[j], packing_position) + distance(sorting_position, packing_position)
                            robots_positions[j] = sorting_position
                            robot_time[j] = time_list2[task_index]
                            dict2[rob].remove(dict4[rob][i])
                    if dict4[rob][i][1] == 1:
                        break
        return dict2, robot_time, time_list, time_list2


    def fit(data, k):
        # 5 robot
        robots_positions = [ [1,25],[1, 26], [1, 27], [1, 28],[1,29],[1,30],[1,31],[1,32] ]
        dict1 = {}
        # 20 --> 30
        list1 = [i for i in range(40)]
        for i in range(data.shape[2]):
            if str(data[k][0][i]) not in dict1.keys():
                dict1[f'{data[k][0][i]}'] = []
            if data[k][1][i] in list1:
                dict1[f'{data[k][0][i]}'].append((data[k][1][i], 1))
                list1.remove(data[k][1][i])
            else:
                dict1[f'{data[k][0][i]}'].append((data[k][1][i], 2))
        dict2 = copy.deepcopy(dict1)
        # 5 robot
        robot_time = [0]*6

        # 20 --> 30
        time_list = [99999] * 40
        # 5 robot
        for j in range(6):
            rob = str(j)
            if rob in dict1:
                time = 0
                for i in range(len(dict1[rob])):
                    if dict1[rob][i][1] == 1 and i == 0:
                        time_list[dict1[rob][i][0]] = distance(robots_positions[j], tasks[dict1[rob][i][0]]) + time + distance(tasks[dict1[rob][i][0]], packing_position)
                        time = time_list[dict1[rob][i][0]]
                        robots_positions[j] = packing_position
                        dict2[rob].remove(dict1[rob][i])
                        robot_time[j] = time_list[dict1[rob][i][0]]
                    elif dict1[rob][i][1] == 1 and i != 0:
                        time_list[dict1[rob][i][0]] = distance(tasks[dict1[rob][i][0]], packing_position) + time + distance(robots_positions[j], tasks[dict1[rob][i][0]])
                        time = time_list[dict1[rob][i][0]]
                        robots_positions[j] = packing_position
                        dict2[rob].remove(dict1[rob][i])
                        robot_time[j] = time_list[dict1[rob][i][0]]
                    if dict1[rob][i][1] == 2:
                        break
        # 20 --> 30
        time_list2 = [99999] * 40
        # 5 robot
        for j in range(6):
            rob = str(j)
            if rob in dict1:
                for i in range(len(dict1[rob])):
                    if dict1[rob][i][1] == 2:
                        task_index = dict1[rob][i][0]
                        task_2_start = max(time_list[task_index], robot_time[j])
                        if task_2_start == 99999:
                            break
                        else:
                            time_list2[task_index] = task_2_start + distance(robots_positions[j], packing_position) + distance(sorting_position, packing_position)
                            robots_positions[j] = sorting_position
                            robot_time[j] = time_list2[task_index]
                            dict2[rob].remove(dict1[rob][i])
                    if dict1[rob][i][1] == 2:
                        break
        while any(len(value) != 0 for value in dict2.values()):
            dict2, robot_time, time_list, time_list2 = method1(dict2, robot_time, time_list, time_list2)
    #         print(dict2)
            dict2, robot_time, time_list, time_list2 = method2(dict2, robot_time, time_list, time_list2)
    #         print(dict2)

        time_1_df = time_restrict(list(time_list + tasks_time))
        time_list2_s = [value - distance(sorting_position, packing_position) for value in time_list2]
        time_list2_list = []
        for index,t in enumerate(time_list2_s):
            time_list2_list.append([index,t])
            time_list2_df = pd.DataFrame(time_list2_list)
            time_list2_df.columns = ['task', 'time']
            time_list2_df.sort_values(by='time', inplace=True)

        for i in range(len(time_list2_df)):
            task_id = time_list2_df.iloc[i,0]
            t1 = time_1_df[time_1_df['task'] == task_id].iloc[0,1]
            t2 = time_list2_df.iloc[i,1]
            if t1 > t2:
                time_list2_df.iloc[i,1] = t1

        finish_time = max(time_list2_df['time'] + sorters_time) + distance(sorting_position, packing_position)

        return robot_time, dict2, time_list, time_list2, dict1, finish_time


    def fitness_caculate(data):
        result = []
        for i in range(data.shape[0]):
            robot_time, dict2, time_list, time_list2, dict1, finish_time = fit(data, i)
            result.append([time_list, time_list2, dict1, finish_time, data[i]])
        return result


    def cross(parent1, parent2):
        crossover_point = random.randint(1, len(parent1[4][0]) - 1)
        child1 = np.stack((np.concatenate((parent1[4][0][:crossover_point], parent2[4][0][crossover_point:]), axis=0), parent1[4][1]), axis=0)
        child2 = np.stack((np.concatenate((parent1[4][0][:crossover_point], parent2[4][0][crossover_point:]), axis=0), parent2[4][1]), axis=0)
        return child1, child2


    def mutation(par):
        parent = copy.deepcopy(par)
        mut1 = random.randint(0, len(parent[4][0]) - 1)
        mut2 = random.randint(0, len(parent[4][0]) - 1)

        parent[4][0][mut1], parent[4][0][mut2] = parent[4][0][mut2], parent[4][0][mut1]
        parent[4][1][mut1], parent[4][1][mut2] = parent[4][1][mut2], parent[4][1][mut1]

        return parent[4]


    def Swiss_chakra(total_genetic):
        P_baoleng = 0.1
        total_genetic['score'] = [0]*180
        idx = random.sample(range(180), 180)
        group1 = idx[:45]
        group2 = idx[45:90]
        group3 = idx[90:135]
        group4 = idx[135:180]

        # 第一轮
        for i in range(45):
            r = random.random()
            if total_genetic.iloc[group1[i],3] >= total_genetic.iloc[group2[i],3] and r > P_baoleng:
                total_genetic.iloc[group2[i],5] += 1
            if total_genetic.iloc[group1[i],3] >= total_genetic.iloc[group2[i],3] and r < P_baoleng:
                total_genetic.iloc[group1[i],5] += 1
            if total_genetic.iloc[group1[i],3] < total_genetic.iloc[group2[i],3] and r > P_baoleng:
                total_genetic.iloc[group1[i],5] += 1
            if total_genetic.iloc[group1[i],3] < total_genetic.iloc[group2[i],3] and r < P_baoleng:
                total_genetic.iloc[group2[i],5] += 1

            r1 = random.random()
            if total_genetic.iloc[group3[i],3] >= total_genetic.iloc[group4[i],3] and r1 > P_baoleng:
                total_genetic.iloc[group4[i],5] += 1
            if total_genetic.iloc[group3[i],3] >= total_genetic.iloc[group4[i],3] and r1 < P_baoleng:
                total_genetic.iloc[group3[i],5] += 1
            if total_genetic.iloc[group3[i],3] < total_genetic.iloc[group4[i],3] and r1 > P_baoleng:
                total_genetic.iloc[group3[i],5] += 1
            if total_genetic.iloc[group3[i],3] < total_genetic.iloc[group4[i],3] and r1 < P_baoleng:
                total_genetic.iloc[group4[i],5] += 1
        group_score1 = total_genetic[total_genetic['score'] == 1]
        group_score0 = total_genetic[total_genetic['score'] == 0]

        # 第二轮
        idx2 = random.sample(range(90), 90)
        group1_1 = idx2[:45]
        group1_2 = idx2[45:]
        idx3 = random.sample(range(90), 90)
        group0_1 = idx3[:45]
        group0_2 = idx3[45:]
        for i in range(45):
            r = random.random()
            if group_score1.iloc[group1_1[i], 3] >= group_score1.iloc[group1_2[i], 3] and r > P_baoleng:
                group_score1.iloc[group1_2[i], 5] += 1
            if group_score1.iloc[group1_1[i], 3] >= group_score1.iloc[group1_2[i], 3] and r < P_baoleng:
                group_score1.iloc[group1_1[i], 5] += 1
            if group_score1.iloc[group1_1[i], 3] < group_score1.iloc[group1_2[i], 3] and r > P_baoleng:
                group_score1.iloc[group1_1[i], 5] += 1
            if group_score1.iloc[group1_1[i], 3] < group_score1.iloc[group1_2[i], 3] and r < P_baoleng:
                group_score1.iloc[group1_2[i], 5] += 1

            r = random.random()
            if group_score0.iloc[group0_1[i], 3] >= group_score0.iloc[group0_2[i], 3] and r > P_baoleng:
                group_score0.iloc[group0_2[i], 5] += 1
            if group_score0.iloc[group0_1[i], 3] >= group_score0.iloc[group0_2[i], 3] and r < P_baoleng:
                group_score0.iloc[group0_1[i], 5] += 1
            if group_score0.iloc[group0_1[i], 3] < group_score0.iloc[group0_2[i], 3] and r > P_baoleng:
                group_score0.iloc[group0_1[i], 5] += 1
            if group_score0.iloc[group0_1[i], 3] < group_score0.iloc[group0_2[i], 3] and r < P_baoleng:
                group_score0.iloc[group0_2[i], 5] += 1
        group_score_2_2 = group_score1[group_score1['score'] == 2] # 晋级45
        group_score_2_0 = group_score0[group_score0['score'] == 0]
        group_score_2_1 = pd.concat((group_score1[group_score1['score'] == 1], group_score0[group_score0['score'] == 1]))

        # 第三轮
        idx4 = random.sample(range(90), 90)
        group0_3_1 = idx4[:45]
        group0_3_2 = idx4[45:]
        for i in range(45):
            r = random.random()
            if group_score_2_1.iloc[group0_3_1[i], 3] >= group_score_2_1.iloc[group0_3_2[i], 3] and r > P_baoleng:
                group_score_2_1.iloc[group0_3_2[i], 5] += 1
            if group_score_2_1.iloc[group0_3_1[i], 3] >= group_score_2_1.iloc[group0_3_2[i], 3] and r < P_baoleng:
                group_score_2_1.iloc[group0_3_1[i], 5] += 1
            if group_score_2_1.iloc[group0_3_1[i], 3] < group_score_2_1.iloc[group0_3_2[i], 3] and r > P_baoleng:
                group_score_2_1.iloc[group0_3_1[i], 5] += 1
            if group_score_2_1.iloc[group0_3_1[i], 3] < group_score_2_1.iloc[group0_3_2[i], 3] and r < P_baoleng:
                group_score_2_1.iloc[group0_3_2[i], 5] += 1
        group_score_3_2 = group_score_2_1[group_score_2_1['score'] == 2] # 晋级45
        group_score_3_1 = group_score_2_1[group_score_2_1['score'] == 1]

        # 第四轮
        group_score_4_0 = group_score_2_0.sort_values(by='fitness')[:15]
        group_4 = pd.concat((group_score_3_1, group_score_4_0))
        group_4['score'] = [1] * 60
        idx5 = random.sample(range(60), 60)
        group0_4_1 = idx5[:30]
        group0_4_2 = idx5[30:]
        for i in range(30):
            r = random.random()
            if group_4.iloc[group0_4_1[i], 3] >= group_4.iloc[group0_4_2[i], 3] and r > P_baoleng:
                group_4.iloc[group0_4_2[i], 5] += 1
            if group_4.iloc[group0_4_1[i], 3] >= group_4.iloc[group0_4_2[i], 3] and r < P_baoleng:
                group_4.iloc[group0_4_1[i], 5] += 1
            if group_4.iloc[group0_4_1[i], 3] < group_4.iloc[group0_4_2[i], 3] and r > P_baoleng:
                group_4.iloc[group0_4_1[i], 5] += 1
            if group_4.iloc[group0_4_1[i], 3] < group_4.iloc[group0_4_2[i], 3] and r < P_baoleng:
                group_4.iloc[group0_4_2[i], 5] += 1
        group_score_4_2 = group_4[group_4['score'] == 2] # 晋级30

        # 最后一轮
        last_group = pd.concat((group_score_4_2, group_score_3_2, group_score_2_2))
        idx6 = random.sample(range(120), 120)
        group0_5_1 = idx6[:60]
        group0_5_2 = idx6[60:]
        for i in range(60):
            r = random.random()
            if last_group.iloc[group0_5_1[i], 3] >= last_group.iloc[group0_5_2[i], 3] and r > P_baoleng:
                last_group.iloc[group0_5_2[i], 5] += 1
            if last_group.iloc[group0_5_1[i], 3] >= last_group.iloc[group0_5_2[i], 3] and r < P_baoleng:
                last_group.iloc[group0_5_1[i], 5] += 1
            if last_group.iloc[group0_5_1[i], 3] < last_group.iloc[group0_5_2[i], 3] and r > P_baoleng:
                last_group.iloc[group0_5_1[i], 5] += 1
            if last_group.iloc[group0_5_1[i], 3] < last_group.iloc[group0_5_2[i], 3] and r < P_baoleng:
                last_group.iloc[group0_5_2[i], 5] += 1
        final_group = last_group[last_group['score'] == 3]
        del final_group['score']
        return final_group


    tasks = np.array([ [11, 26], [13, 18], [15, 22], [20, 25], [22, 30],
                       [24, 13], [28, 14], [30, 17], [32, 14], [34, 18],
                       [10, 22], [12, 26], [16, 29], [20, 30], [23, 33],
                           [24, 34], [29, 13], [31, 25], [33, 29], [14, 17],
                       [10, 9], [10, 10], [10, 13], [10, 14], [10, 17], [10, 18], [10, 21], [10, 25], [10, 26],
                       [10, 29],[24, 13], [28, 14], [30, 17], [32, 14], [34, 18],
                         [10, 22], [12, 26], [16, 29], [20, 30], [23, 33]
                              ])
    # 20->30
#     [24, 13], [28, 14], [30, 17], [32, 14], [34, 18],
#     [10, 22], [12, 26], [16, 29], [20, 30], [23, 33],
#     [24, 34], [29, 13], [31, 25], [33, 29], [14, 17],
# [10, 9], [10, 10], [10, 13], [10, 14], [10, 17], [10, 18], [10, 21], [10, 25], [10, 26], [10, 29],
# [11, 9], [11, 10], [11, 13], [11, 14], [11, 17], [11, 18], [11, 21], [11, 25], [11, 29], [11, 30],[12, 18], [12, 21], [12, 25], [12, 29], [12, 30]
    tasks_time = np.array([20] * 40)
    sorters_time = np.array([20] * 40)

    robots_positions = [ [1,25],[1, 26], [1, 27], [1, 28],[1,29],[1,30],[1,31]]
    packing_position = [2, 19]
    sorting_position = [18, 2]
    pop_num = 80
    dis2time = 1
    generations = 70
    cross_ratio = 0.6
    muta_ratio = 0.1


    population = np.stack([create_chromosome(len(tasks), len(robots_positions)) for _ in range(pop_num)])


    k = 0
    num = 0
    history = []
    best_result = 9999
    t1 = time.time()

    result = pd.DataFrame(fitness_caculate(population))
    # result.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
    # sorted_result = result.sort_values(by='fitness')
    # best_genetic = sorted_result[:20]
    # other_genetic = sorted_result[20:]

    while k < 20:
        num += 1

        result.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
        # 打乱
        shuffled_result = result.sample(frac=1).reset_index(drop=True)
    #     sorted_result = result.sort_values(by='fitness')
    #     best_genetic = sorted_result[:20]
    #     other_genetic = sorted_result[20:]

        new_population = []
        [new_population.append(mutation(shuffled_result.iloc[i,:])) for i in range(60)]
        random_rank = random.sample(range(60), 60)
        for i in range(30):
            child1, child2 = cross(shuffled_result.iloc[random_rank[i],:], shuffled_result.iloc[random_rank[59 - i],:])
            new_population.append(child1)
            new_population.append(child2)
        next_genetic = pd.DataFrame(fitness_caculate(np.array(new_population)))
        next_genetic.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
        next_genetic = pd.concat([next_genetic, shuffled_result])
        next_genetic = next_genetic.sort_values(by='fitness')

        # 优质基因和轮盘基因
        best_genetic = pd.DataFrame(next_genetic[:20])
        total_genetic = pd.DataFrame(next_genetic[20:])


        cmped_genetic = Swiss_chakra(total_genetic)

        result = pd.concat([best_genetic, cmped_genetic])
        result_sorted = result.sort_values(by='fitness')

        history.append(result_sorted.iloc[0,:])
        best_result_ = best_result
        best_result = min(result_sorted.iloc[0,3], best_result)
        if best_result == best_result_:
            k += 1
        else:
            k = 0
        t2 = time.time()
        print(f'第{num}代最优值：{result_sorted.iloc[0,3]}，第{k}次保持最优不变，用时{t2 - t1}s')

        with open("./data_1.csv",'a',encoding="utf_8_sig")as csvfile:
            fieldnames = ['id','result','status','timestamp']
            writer = csv.DictWriter(csvfile,fieldnames=fieldnames)
            writer.writerow({"id": '第{}代最优值'.format(num),"result":result_sorted.iloc[0,3],"status": '第{}次保持最优不变'.format(k),"timestamp": "用时{}s".format(t2 - t1)})





    k = 0
    num = 0
    history1 = []
    best_result = 9999
    t1 = time.time()
    cross_num = int(cross_ratio * pop_num)
    muta_num = int(muta_ratio * pop_num)
    result = pd.DataFrame(fitness_caculate(population))
    result.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
    while k < 20:
        num += 1
        result.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
        sorted_result = result.sort_values(by='fitness')

        new_population = []
        random_rank = random.sample(range(cross_num), cross_num)
        for i in range(int(cross_num / 2)):
            child1, child2 = cross(sorted_result.iloc[random_rank[i],:], sorted_result.iloc[random_rank[cross_num -1 - i],:])
            new_population.append(child1)
            new_population.append(child2)

        random_muta = random.sample(range(len(sorted_result)), muta_num)
        [new_population.append(mutation(sorted_result.iloc[random_muta[i],:])) for i in range(muta_num)]

        next_genetic = pd.DataFrame(fitness_caculate(np.array(new_population)))
        next_genetic.columns = ['time1', 'time2', 'task_seq', 'fitness', 'genetic']
        total_genetic = pd.concat([sorted_result, next_genetic])

        result_sorted = total_genetic.sort_values(by='fitness')
        result = result_sorted.iloc[:,:80]
        history1.append(result_sorted.iloc[0,:])
        best_result_ = best_result
        best_result = min(result_sorted.iloc[0,3], best_result)
        if best_result == best_result_:
            k += 1
        else:
            k = 0
        t2 = time.time()
        print(f'第{num}代最优值：{result_sorted.iloc[0,3]}，第{k}次保持最优不变，用时{t2 - t1}s')


        with open("./data_1_main.csv",'a',encoding="utf_8_sig")as csvfile:
            fieldnames = ['id','result','status','timestamp']
            writer = csv.DictWriter(csvfile,fieldnames=fieldnames)
            writer.writerow({"id": '第{}代最优值'.format(num),"result":result_sorted.iloc[0,3],"status": '第{}次保持最优不变'.format(k),"timestamp": "用时{}s".format(t2 - t1)})


    T += 1